package order

import (
	"fmt"
	"math"
	"math/rand"
	"strconv"
	"time"
)

func GetArry(count int) []int {
	arr := make([]int, count)
	rand.Seed(time.Now().UnixNano())
	for i := 0; i < count; i++ {
		arr[i] = rand.Intn(100)
	}
	return arr
}

func Print(arr []int) {
	fmt.Println("打印:")
	for _, k := range arr {
		fmt.Println(k)
	}
}

//冒泡排序
func BubbleSort(arr []int) []int {
	l := len(arr)
	count := 0
	for i := 0; i < l-1; i++ {
		for j := 0; j < l-1-i; j++ {
			if arr[j] > arr[j+1] {
				tmp := arr[j+1]
				arr[j+1] = arr[j]
				arr[j] = tmp
			}
			count++
		}
	}
	fmt.Println("冒泡排序次数：", count)
	return arr
}

//选择排序
func SelectSort(arr []int) []int {
	l := len(arr)
	var minindex, tmp, count int
	for i := 0; i < l-1; i++ {
		minindex = i
		for j := i + 1; j < l; j++ {
			if arr[j] < arr[minindex] {
				minindex = j
			}
			count++
		}
		tmp = arr[i]
		arr[i] = arr[minindex]
		arr[minindex] = tmp
	}
	fmt.Println("选择排序次数：", count)
	return arr
}

//插入排序
func InsertSort(arr []int) []int {
	l := len(arr)
	var preindex, curr int
	for i := 1; i < l; i++ {
		preindex = i - 1
		curr = arr[i]
		for preindex >= 0 && arr[preindex] > curr {
			arr[preindex+1] = arr[preindex]
			preindex--
		}
		arr[preindex+1] = curr
	}
	return arr
}

func ShellSort(arr []int) []int {
	l := len(arr)
	middle := math.Floor(float64(l / 2))
	for gap := int(middle); gap > 0; gap = int(math.Floor(float64(gap / 2))) {
		for i := gap; i < l; i++ {
			j := i
			curr := arr[i]
			for j-gap >= 0 && curr < arr[j-gap] {
				arr[j] = arr[j-gap]
				j = j - gap
			}
			arr[j] = curr
		}
	}
	return arr
}

func mergeSort(arr []int, start, end int) {
	if start >= end {
		return
	}
	mid := (start + end) / 2
	mergeSort(arr, start, mid)
	mergeSort(arr, mid+1, end)
	merge(arr, start, mid, end)
}

func merge(arr []int, start, mid, end int) {
	var tmparr = []int{}
	var s1, s2 = start, mid + 1
	for s1 <= mid && s2 <= end {
		if arr[s1] > arr[s2] {
			tmparr = append(tmparr, arr[s2])
			s2++
		} else {
			tmparr = append(tmparr, arr[s1])
			s1++
		}
	}
	if s1 <= mid {
		tmparr = append(tmparr, arr[s1:mid+1]...)
	}
	if s2 <= end {
		tmparr = append(tmparr, arr[s2:end+1]...)
	}
	for pos, item := range tmparr {
		arr[start+pos] = item
	}
}

var conunt = 0

func QuickSort(arr []int, first, end int) {
	flag := first
	left := first
	right := end

	if first >= end {
		return
	}

	for first < end {
		for first < end {
			if arr[end] >= arr[flag] {
				end--
				continue
			}
			arr[end], arr[flag] = arr[flag], arr[end]
			flag = end
			conunt++
			break
		}
		for first < end {
			if arr[first] <= arr[flag] {
				first++
				continue
			}
			arr[first], arr[flag] = arr[flag], arr[first]
			flag = first
			conunt++
			break
		}
	}
	QuickSort(arr, left, flag-1)
	QuickSort(arr, flag+1, right)
}

func quickSort(arr []int, start, end int) {
	if start < end {
		i, j := start, end
		key := arr[(start+end)/2]
		for i <= j {
			for arr[i] < key {
				i++
			}
			for arr[j] > key {
				j--
			}
			if i <= j {
				arr[i], arr[j] = arr[j], arr[i]
				i++
				j--
			}
		}
		if start < j {
			quickSort(arr, start, j)
		}
		if end > i {
			quickSort(arr, i, end)
		}
	}
}

//堆排序
func HeapSort(arr []int) {
	n := len(arr) - 1
	for k := n / 2; k >= 1; k-- {
		sink(arr, k, n)
	}
	for n > 1 {
		swap(arr, 1, n)
		n--
		sink(arr, 1, n)
	}
}

func sink(s []int, k, n int) {
	for {
		i := 2 * k
		if i > n {
			break
		}
		if i < n && s[i+1] > s[i] {
			i++
		}
		if s[k] >= s[i] {
			break
		}
		swap(s, k, i)
		k = i
	}
}

func swap(s []int, i, j int) {
	s[i], s[j] = s[j], s[i]
}

//计数排序
func CountingSort(arr []int) []int {
	biger := GetArryMax(arr)
	fmt.Println("zuida:", biger)
	orderarr := make([]int, biger+1)
	for _, v := range arr {
		orderarr[v]++
	}
	var resarr []int
	for i, v := range orderarr {
		if v > 0 {
			for j := 1; j <= v; j++ {
				resarr = append(resarr, i)
			}
		}
	}
	return resarr
}

func GetArryMax(arr []int) int {
	biger := 0
	for _, v := range arr {
		if v > biger {
			biger = v
		}
	}
	return biger
}

//桶排序
func BucketSort(arr []int) []int {
	num := len(arr)
	max := GetArryMax(arr)
	buckets := make([][]int, num)

	index := 0
	for i := 0; i < num; i++ {
		index = arr[i] * (num - 1) / max
		buckets[index] = append(buckets[index], arr[i])
	}

	tmpPos := 0
	for i := 0; i < num; i++ {
		bucketLen := len(buckets[i])
		if bucketLen > 0 {
			SortInBucket(buckets[i])
			copy(arr[tmpPos:], buckets[i])
			tmpPos += bucketLen
		}
	}
	return arr
}

func SortInBucket(arr []int) {
	length := len(arr)
	if length <= 1 {
		return
	}
	for i := 1; i < length; i++ {
		backup := arr[i]
		j := i - 1
		for j >= 0 && backup < arr[j] {
			arr[j+1] = arr[j]
			j--
		}
		arr[j+1] = backup
	}
}

func RadixSort(arr []int) {
	maxValLen := 0
	for i := 0; i < len(arr); i++ {
		n := len(strconv.Itoa(arr[i]))
		if n > maxValLen {
			maxValLen = n
		}
	}
	for loc := 1; loc <= maxValLen; loc++ {
		Sort(arr, loc)
	}
}

func Sort(arr []int, loc int) {
	bucket := make([][]int, 10)
	for i := 0; i < len(arr); i++ {
		ji := digit(arr[i], loc)
		if bucket[ji] == nil {
			bucket[ji] = make([]int, 0)
		}
		bucket[ji] = append(bucket[ji], arr[i])
	}

	idx := 0
	for i := 0; i <= 9; i++ {
		for j := 0; j < len(bucket[i]); j++ {
			arr[idx] = bucket[i][j]
			idx++
		}
	}
}

func digit(num int, loc int) int {
	return num % int(math.Pow10(loc)) / int(math.Pow10(loc-1))
}
